package com.dyz.LeetCodeforSwordFingerOffer;



import java.util.ArrayList;

/**
 * @author: daiyizheng
 * @date: 2021/7/6 21:38
 * @description:
 */
public class TreeToDoublyList36 {
    public static void main(String[] args) {
        Node1 root = new Node1(4);
        Node1 node1 = new Node1(2);
        Node1 node2 = new Node1(5);
        Node1 node3 = new Node1(1);
        Node1 node4 = new Node1(3);
//        Node1 node5 = new Node1(14);
//        Node1 node6 = new Node1(16);
        node1.left = node3;
        node1.right = node2;
//        node5.left = node4;
//        node5.right = node6;
        root.left = node1;
//        root.right = node5;
        Node1 node11 = new TreeToDoublyList36().treeToDoublyList(root);
        System.out.println(node11);
    }
    //中序遍历，节点放入数组，连个遍历双向链接
    public Node1 treeToDoublyList(Node1 root) {
        if(root==null){
            return root;
        }
        ArrayList<Node1> arrayList = new ArrayList<>();
        InOrder(root, arrayList);
        Node1 head = arrayList.get(0);
        head.left = null;
        Node1 pre = head;
        for(int i=1; i<arrayList.size();i++){
            pre.right = arrayList.get(i);
            arrayList.get(i).left = pre;
            pre = pre.right;
        }
        return head;

    }
    private void InOrder(Node1 root, ArrayList<Node1> arrayList){
        if(root.left!=null){
            InOrder(root.left, arrayList);
        }

        arrayList.add(root);

        if(root.right!=null){
            InOrder(root.right, arrayList);
        }
    }
}
class Node1 {
    public int val;
    public Node1 left;
    public Node1 right;

    public Node1() {}

    public Node1(int _val) {
        val = _val;
    }

    public Node1(int _val,Node1 _left,Node1 _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
